package combination;

import java.util.HashMap;
import java.util.Map;

/**
 * 377. 组合总和 Ⅳ------记忆化递归/动态规划
 * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
 * 请你从 nums 中找出并返回总和为 target 的元素组合的个数。
 * <p>
 * 题目数据保证答案符合 32 位整数范围。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-01 17:41
 */
public class L377 {
    //    递归
//    int count=0;
//    public int combinationSum4(int[] nums, int target) {
//        dfs(nums, target);
//        return count;
//    }
//    public void dfs(int[] nums, int target){
//        if(target<0) return;
//        if(target==0){
//            count++;
//        }
//        for (int i = 0; i <nums.length ; i++) {
//            target-=nums[i];
//            dfs(nums, target);
//            target+=nums[i];
//        }
//    }
//记忆化递归，time: n*terget
    Map<Integer, Integer> map = new HashMap<>();

    public int combinationSum4(int[] nums, int target) {
        map.put(0, 1);//target=0时，count+1；
        return dfs(nums, target);

    }

    public int dfs(int[] nums, int target) {
        if (map.containsKey(target)) {
            return map.get(target);
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i]) {
                count += dfs(nums, target - nums[i]);
            }
        }
        map.put(target, count);
        return count;
    }

    public static void main(String[] args) {
        L377 l377 = new L377();
        int i = l377.combinationSum4(new int[]{1, 2, 3}, 32);
        System.out.println(i);
    }
}
